iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 12
0
自我挑戰組

學習資料結構30天系列 第 12

[Data Structure][Graph] - Kruskal's Algorithm!

  • 分享至 

  • xImage
  •  

前言

昨天介紹了Mininum spanning tree,找Mininum spanning tree的方法有Kruskal's AlgorithmPrim's Algorithm,今天先介紹Kruskal's Algorithm

註: Borůvka's Algorithm 也是找Mininum spanning tree的方法,這三種方法較為著名,皆為貪婪演算法

  • Greedy method,特性是每個階段都能得到最好的結果,最後的結果也是最好的

Kruskal's Algorithm

依次找尋圖形中加權值最小的邊加入spanning tree,嘗試連結圖的N個頂點,但不使用會造成圖形成環路的邊,直到產生N-1個邊。

  • 又到了以圖片為例子的時間了:
    https://ithelp.ithome.com.tw/upload/images/20181026/20112438KmBsa0J2B5.jpg
    1. 先找出圖中權重最小的邊是1,所以邊EG連上
      https://ithelp.ithome.com.tw/upload/images/20181026/20112438AtIxQZQVjd.jpg
    2. 圖中權重次小的邊是2,所以邊DE連上
      https://ithelp.ithome.com.tw/upload/images/20181026/20112438TKHT5sHzO2.jpg
    3. 圖中剩下的邊裡面權重最小是3,所以邊AD連上
      https://ithelp.ithome.com.tw/upload/images/20181026/20112438ZiGpBK0b7G.jpg
    4. 圖中剩下的邊裡面權重最小是4,所以邊CE連上
      https://ithelp.ithome.com.tw/upload/images/20181026/20112438dtN8dxv3A0.jpg
    5. 找出圖中剩下的邊裡面權重最小是6,圖中藍邊AC和綠邊BC權重都是6
      https://ithelp.ithome.com.tw/upload/images/20181026/201124384EX56lnLUY.jpg
    6. 若選擇邊AC會造成環路,所以選擇BC
      https://ithelp.ithome.com.tw/upload/images/20181026/20112438tk8pmBXFfc.jpg
    7. 圖中剩下的邊裡面權重最小是8,,但會造成環路,所以AB邊不連接
      https://ithelp.ithome.com.tw/upload/images/20181026/20112438CDw6i1aEDC.jpg
    8. 圖中剩下的邊裡面權重最小是9,,但會造成環路,所以CG邊不連接
      https://ithelp.ithome.com.tw/upload/images/20181026/20112438tN9dcuWRg6.jpg
    9. 最後找到的Minimum spanning tree
      https://ithelp.ithome.com.tw/upload/images/20181026/20112438ZQjuZg4N15.jpg

明天介紹Prim's Algorithm

參考

細談資料結構 第六版
ISBN 978-986-312-014-8


上一篇
[Data Structure][Graph] - Minimum Spanning Tree
下一篇
[Data Structure][Graph] - Prim's Algorithm
系列文
學習資料結構30天30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言